package Demo5;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/valid-triangle-number/
 * 有效的三角形个数
 * 1. 先排序,利用单调性
 * 2. 固定最大值
 * 3. 使用双指针 来判断和统计
 * 三角形的计算方法
 * a <= b <= c
 * 只要满足以上条件, b + b 大于c  那a 和b 之间的任何数加上b 都大于c
 *
 */
class Solution {
    public int triangleNumber(int[] nums) {
        // 1. 先排序
        Arrays.sort(nums);
        int ret = 0,n = nums.length;
        for(int i = nums.length - 1; i >= 2 ;i--) {
            int left = 0,right = i - 1;
            while(left < right) {
                if(nums[left] + nums[right] > nums[i]) {
                    // 大于就计数,然后right -- 前往下一个区间统计个数
                    ret += right - left;
                    right--;
                }else {
                    // 小于,left就加加
                    left++;
                }
            }
        }
        return ret;
    }
}